\section{A unified perspective on GRE} \label{sec:related}


Viewing GRE as a problem of generating DL formulas offers a unified
perspective: It is the problem of computing a DL
formula with a given extension.  Many existing approaches can be
subsumed under this view; we have summarized this for some of them in
Fig.~\ref{fig:related}, along with the DL fragment they use.  We
already discussed some of these approaches in Section~\ref{sec:gre}.
Furthermore, the non-relational but negative and disjunctive
descriptions generated by \newcite{deemter02:_gener_refer_expres} are
simply formulas of $\mathcal{PL}$; and
\newcite{gardent02:_gener_minim_defin_descr} generalizes this into
generating formulas of $\mathcal{ELU}_{(\neg)}$, i.e., \el\ plus
disjunction and atomic negation.  The approach presented here fits
well into this landscape, and it completes the picture by showing how
to generate REs in \alc, which combines all connectives used in any of
these previous approaches.


Where our approach breaks new ground is in the way these formulas are
computed: It successively refines a decomposition of the domain into
subsets.  In this way, it is reminiscent of the Incremental Algorithm,
which in fact can be seen as a special case of the \el\ algorithm.
However, unlike \newcite{dale91:_gener_refer_expres_invol_relat} and
its successors, such as
\newcite{kelleher06:_increm_gener_of_spatial_refer}, we do not have to
take special precautions to avoid infinite regress. While Dale and
Haddock's algorithm attempts to generate a RE for a single individual,
for successive individuals in the model, our algorithms consider all
individuals in parallel.  It monotonically refines a partition of the
model and never needs to backtrack, and therefore is always guaranteed
to terminate.


\begin{figure}
  \centering
  \begin{small}
  \begin{tabular}{l|p{0.2\textwidth}}
    GRE algorithm & DL variant \\ \hline
    \newcite{Dale1995} & $\mathcal{CL}$ \\
    \newcite{deemter02:_gener_refer_expres} & $\mathcal{PL}$ \\
    \newcite{dale91:_gener_refer_expres_invol_relat} & \el \\
    \newcite{kelleher06:_increm_gener_of_spatial_refer} & \el \\
    \newcite{gardent02:_gener_minim_defin_descr} & $\mathcal{ELU}_{(\neg)}$\\
%    \newcite{Krahmer2003} & \el\ + equality between individuals
  \end{tabular}
  \end{small}
  \caption{DL variants used by different GRE algorithms.}
  \label{fig:related}\vspace*{-1.5ex}
\end{figure}

Perhaps closest in spirit to our approach is Krahmer et al.'s graph
algorithm~\shortcite{Krahmer2003}, which also computes REs by
extending them successively.  However, their subgraphs go beyond the
expressive power of \alc\ in that they can distinguish between ``the
dog that bites a dog'' and ``the dog that bites itself''.  The price
they pay for this increase in expressive power is an NP-complete
worst-case complexity.  Interestingly, Krahmer et al.\ themselves
discuss the possibility of seeing their subgraphs as formulas of
hybrid logic which are satisfied at the points where the subgraph can
be embedded; and hybrid logics can be seen as very expressive
description logics \cite{arec:hybr05b}.

%The graphs  use to represent referring
%expressions go beyond DL in that they can express equality between
%individuals. For example, Krahmer et al. could distinguish a dog that
%bites itself from dogs that bite other dogs; a distinction which
%cannot be made using description logic formulas. Their referring
%expressions can be seen as formulas of a hybrid logic (another related
%and well-studied family of logics \todo{citation?? or do we want to
%mention hybrid logic at all?}), more specifically the logic \el\ +
%equality between individuals.










%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "dl-gre-08"
%%% End: 
